;;; b-day.lisp
;;; The Birthday Problem

(defpackage :b-day
  (:use :common-lisp)
  (:export :lbd :b-day :pf :newton :fact))

(in-package :b-day)

; (export '(lbd b-day pf newton fact))

(defun lbd () (load "b-day.lisp"))

(defun b-day-problem-alpha (n a)
 (/
 (- n (- a 1 ))
 n)
)

(defun b-day-problem (n a)
  (
   if (= a 1)
      1 
      (* 
       (b-day-problem-alpha n a)  
       (b-day-problem n (- a 1))
       )
      )
  )

; usage:  (b-day 365 25) for the birthday problem with 25 people.
(defun b-day (n a) (- 1.0 (b-day-problem n a)))

(defun divides (n a) (= 0 (mod n a)))


; a > 2
; a is odd
(defun smallest-factor-gt (n a)
  ( if (divides n a) a
       (if (> (* a a) n) n
      (smallest-factor-gt n (+ a 2)))))


(defun small-fact (n)
  (
   if (divides n 2) 2
( loop for i from 3 to n by 2
        ;  do (format t "~a " i)
        do (if (divides n i) (return i))
        do (if (> (* i i) n) (return n)))))


(defun smallest-factor (n)
  (if (divides n 2) 2
 (smallest-factor-gt n 3)))

(defun prime-factors (n) 
  (if (= 1 n) (list)
       (cons (smallest-factor n) (prime-factors (/ n (smallest-factor n))))
))

(defun prod (n) 
  (if (not (cdr n)) (car n)
      (* (car n) (prod (cdr n)))))


(defun pc (l) (* 1.0 (/ (car (last l)) (prod l))))

(defun pf (n)
  (let* 
      (
       (a 0)
       )
  (loop while (< 1 n)
        do (setf a (small-fact n))
        collect a
      do (setf n (/ n a)))
    )
)
  
  
  
  

(defun pfc (n) 
  (format t "~a~%" (pc (pf n)))
  (pf n))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(defun newton-next (guess target) 
  ( /
    (+ target (* guess guess))
     (* 2 guess)
))

(defun distance (x y) (abs (- x y)))

(defun within (x y d)
  (<= (distance x y) d))

(defun newton (g target accuracy)
  (let* 
      (
       (guess g)
       )
   (loop while (not (within (* guess guess) target accuracy))
         do (format t "~a~%" guess)
         do (setf guess (newton-next guess target)))
         guess)
    )
  

(defun n-ton (target &key (accuracy 1))
  (newton  (/ target 2) target accuracy))

(defun log-average ( a b ) (/ (+ a b) 2))
(defun squared (x) (* x x))

;(defun log-newton-next (low high target)
;   (if (= (squared (log-average low high)) target)
;       (log-average (l) (/ (car (last l)) (prod l))) low high)
;       (if (< (squared (log-average low high)) target)
;            (list (log-average low high) high)
;        (list low (log-average low high)))))


;(defun log-newton (target accuracy)
;  (setf guess (list 1 target))
;   (loop while (not (within (car guess) (cadr guess) accuracy))
;         do (format t "~a~%" (log-average (car guess) (cadr guess)))
;         do (setf guess (log-newton-next (car guess) (cadr guess) target)))
;         (log-average (car guess) (cadr guess)))

(defun nat-nums (n)
  (loop for i from 1 to n collecting i))

;(defun prod (n) 
;  (if (not (cdr n)) (car n)
;      (* (car n) (prod (cdr n)))))



(defun fact (n) (prod (nat-nums n)))

(defun pfact (n) (pf (+ 1 (fact n))))

(defun pfact-all (n)
  (loop for i from 1 to n
        do (format t "~{ ~a ~} ~%" (pfact i))))


;(defun ltimes-mod (l n p result)
;  ( (setf 'result nil)
;    (dolist (elt l) (push (mod (* elt n) p) result))
;    result))


;(defun sum (l) (loop for each elt in l summing elt))

(defmacro rpn ( y u v l x s )
  (+ (* y 3 ) u (* v 2 ) l x (when s 10)))


; end package b-day
(in-package :cl-user)

 

 
